#pragma once

#include <iostream>
#include <exception>
#include <vector>
#include <unordered_map>
#include <functional>

#include <thread>
#include <mutex> 
#include <algorithm>

#include <cstring>
#include <assert.h>
#include <time.h>
// 头文件包含
#ifdef _WIN32 // WIN
#include <Windows.h>
#else // linux
#include <unistd.h>
#include <sys/mman.h>
#include <pthread.h>
#endif

#ifdef _WIN64 // WIN64
typedef unsigned long long PAGE_ID;
#elif _WIN32 // WIN32
typedef size_t PAGE_ID;
#elif __LP64__ // linux64位
typedef unsigned long long PAGE_ID;
#else  // linux32位
typedef size_t PAGE_ID;
#endif

using std::cout;
using std::endl;

static const size_t MAX_BYTES = 256 * 1024;		// 一次提供的最大的内存大小
static const size_t NFREELIST = 208;			// 自由链表的数量
static const size_t NPAGES = 129;				// 页的最大数量
static const size_t PAGE_SHIFT = 12;			// 页的大小 <<量
// 注意：页的大小需要根据所在平台的页确定，一般4KB比较好

inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	// 1 << 13 == 8kb
	void* ptr = VirtualAlloc(0, kpage * (1 << PAGE_SHIFT), MEM_COMMIT | MEM_RESERVE,
		PAGE_READWRITE);
#else
	// linux下brk mmap等
	PAGE_ID length = kpage * (1 << PAGE_SHIFT);
	void *ptr = mmap(NULL, length, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);  
#endif
	if (ptr == nullptr || ptr == MAP_FAILED)
		throw std::bad_alloc();
	return ptr;
}

inline static void SystemFree(void* ptr, size_t size)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else // linux  sbrk unmmap等
	munmap(ptr, size);
#endif
}

static void*& NextBlock(void* block)
{
	assert(block);

	return *(void**)block; // 取前指针的内容
}


class FreeList // 自由链表（适用于threadcache）
{
public:
	void Push(void* block)
	{
		assert(block);
		// 头插
		NextBlock(block) = _freeList;
		_freeList = block;
		_size++;
	}

	void PushRange(void* start, void* end, size_t n)
	{
		assert(start && end);

		NextBlock(end) = _freeList;
		_freeList = start;
		_size += n;
	}

	void PopRange(void*& start, void*& end, size_t n)
	{
		assert(0 < n && n <= _size);

		start = end = _freeList;
		for (size_t i = 0; i < n - 1; ++i)
		{
			end = NextBlock(end);
		}

		_freeList = NextBlock(end);
		NextBlock(end) = nullptr;

		_size -= n;
	}

	void* Pop()
	{
		assert(_freeList);
		void* ret = _freeList;
		_freeList = NextBlock(_freeList);
		_size--;
		return ret;
	}

	size_t Size()
	{
		return _size;
	}

	bool empty()
	{
		return _freeList == nullptr;
	}

	size_t& Get_Fetch_Count()
	{
		return _fetch_count;
	}
private:
	void* _freeList = nullptr;
	size_t _fetch_count = 1; // 一次拿的个数
	size_t _size = 0;
};

class Span // 跨度（管理页）
{
public:
	Span() :_pageid(0), _n(0), _list(nullptr), _blocksize(0), _usecount(0), _isUse(false),
		_prev(nullptr), _next(nullptr)
	{}

	PAGE_ID _pageid;	// 页号
	size_t _n;			// 页数

	void* _list;		// 自由链表（小块）
	size_t _blocksize;	// 块大小（释放size）
	size_t _usecount;	// 引用计数
	bool _isUse;

	Span* _prev;
	Span* _next; 
};

class SpanList // Span双向带头链表（适用于CentralCache）
{
public:
	SpanList()
	{
		_head = new Span;
		_head->_prev = _head;
		_head->_next = _head;
	}

	Span* Begin()
	{
		return _head->_next;
	}

	Span* End()
	{
		return _head;
	}

	void PushFront(Span* newspan)
	{
		assert(newspan);
		assert(_head);
		Insert(_head->_next, newspan);
	}

	Span* PopFront()
	{
		Span* span = _head->_next;
		Ereas(span);
		return span;
	}


	// 在pos位置插入
	void Insert(Span* pos, Span* newspan)
	{
		assert(pos);
		assert(newspan);

		Span* prev = pos->_prev;
		newspan->_next = pos;
		newspan->_prev = prev;
		pos->_prev = newspan;
		prev->_next = newspan;

	}

	void Ereas(Span* pos)
	{
		assert(pos);

		Span* prev = pos->_prev;
		Span* next = pos->_next;
		
		prev->_next = next;
		next->_prev = prev;

		pos->_next = nullptr;
		pos->_prev = nullptr;
		// pos位置的空间并没有释放,只是从链表中拿掉
	}

	bool Empty()
	{
		return _head->_next == _head;
	}

private:
	Span* _head;
public:
	std::mutex _mtx; // 桶锁
};


// 哈希桶size
class ClassSize
{
public:
	static inline size_t _RoundUp(size_t Bytes, size_t AlignNum)
	{
		return (Bytes + AlignNum - 1) & ~(AlignNum - 1);
	}

	static inline size_t _Index(size_t Bytes, size_t AlignNum)
	{
		// (6 + 7) / 8 - 1 == 0
		return (Bytes + AlignNum - 1) / AlignNum - 1;
	}
public:
	// 整体控制在最多10%左右的内碎片浪费
	// [1,128] 8byte对齐						freelist[0,16)
	// [128+1,1024] 16byte对齐				freelist[16,72)
	// [1024+1,8*1024] 128byte对齐			freelist[72,128)
	// [8*1024+1,64*1024] 1024byte对齐		freelist[128,184)
	// [64*1024+1,256*1024] 8*1024byte对齐	freelist[184,208)
	
	// 计算内存块的对齐数
	//static inline size_t _RoundUp(size_t Bytes, size_t AlignNum)
	//{
	//	if (Bytes % AlignNum == 0)
	//		return (Bytes / AlignNum) * AlignNum;
	//	else
	//		return (Bytes / AlignNum + 1) * AlignNum;
	//}

	// 32 16 8 4 2 1
	//  0  0 0 0 0 0 

	// 返回内存块的对齐数
	static inline size_t RoundUp(size_t Bytes)
	{
		if (Bytes <= 128)
		{
			return _RoundUp(Bytes, 8);
		}
		else if (Bytes <= 1024)
		{
			return _RoundUp(Bytes, 16);
		}
		else if (Bytes <= 8 * 1024)
		{
			return _RoundUp(Bytes, 128);
		}
		else if (Bytes <= 64 * 1024)
		{
			return _RoundUp(Bytes, 1024);
		}
		else if (Bytes <= 256 * 1024)
		{
			return _RoundUp(Bytes, 8 * 1024);
		}
		else
		{
			return _RoundUp(Bytes, 1 << PAGE_SHIFT);
		}
		return -1;
	}


	// 根据提供的需要的内存块大小，返回位于哪一个哈希桶
	static inline size_t Index(size_t Bytes)
	{
		assert(Bytes);
		size_t offset[] = { 16,72,128,184 }; // 偏移
		if (Bytes <= 128)
		{
			return _Index(Bytes, 8);
		}
		else if (Bytes <= 1024)
		{
			return _Index(Bytes - 128, 16) + offset[0];
		}
		else if (Bytes <= 8 * 1024)
		{
			return _Index(Bytes - 1024, 128) + offset[1];
		}
		else if (Bytes <= 64 * 1024)
		{
			return _Index(Bytes - 8 * 1024, 1024) + offset[2];
		}
		else if (Bytes <= 256 * 1024)
		{
			return _Index(Bytes - 64 * 1024, 8 * 1024) + offset[3];
		}
		else
		{
			assert(false);
		}
		return -1;
	}

	// threadcache一次向CentralCache获取多少个block
	static inline size_t Nummovesize(size_t size)
	{
		assert(size);

		// [2, 512]
		size_t num = MAX_BYTES / size;
		if (num > 512)
			num = 512;
		if (num < 2)
			num = 2;
		return num;
	}

	// [1, 64]
	// CentralCache向PageCache获取多少大小的page
	static inline size_t Nummovepage(size_t size)
	{
		assert(size);

		size_t npage = Nummovesize(size) * size;
		npage >>= PAGE_SHIFT;

		if (npage == 0)
			npage = 1;
		return npage;
	}
};